package cn.walls1717.dataStructure.sort;

import cn.walls1717.leetcode.util.AlgorithmUtil;

import java.util.Arrays;

/**
 * 选择排序
 *
 * @author walls1717
 * @since 2022-04-28
 **/
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr = {3, 1, 5, 2, 4};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        // 临时变量，存储最小值元素下标
        int small;
        for (int i = 0; i < arr.length - 1; ++i) {
            // 先设置最小值为数组第i个元素
            small = i;
            for (int j = i; j < arr.length; ++j) {
                // 拿到最小值元素下标
                if (arr[j] < arr[small]) {
                    small = j;
                }
            }
            // 如果最小值下标没有发生变化，就不需要进行交换，减少交换次数
            if (small != i) {
                AlgorithmUtil.swap(arr, i, small);
            }
        }
    }
}
